'''
适合有连通或没有连通的图使用Bfs得到的是一条最短路径
'''
from python算法.Graph.Ljt import graph
from collections import deque

class solution():
    def __init__(self,file=None):
        self.cg = graph(file)#创建图对象
        self.G = self.cg.readGraph()#创建图
        self.V  = self.cg.getV
        self.E = self.cg.getE
        self.__visited = [False]*self.V#用来记录多个联通分量的首个Node或者可以说记录图中的节点是否被访问
        self.__BfsQue = deque(maxlen=self.V)
        self.__resBfs = []
        self.__resBfsPath = [-1]*self.V
    def getBfspath(self,origin,target):
        # 判断这两个节点是否连通的  ，
        res = []
        self.__Bfs(origin)
        print(self.__resBfsPath)
        if self.__resBfsPath[target]==-1:
            return None
        cur = target
        res.append(cur)
        while cur!=origin :
            res.append(self.__resBfsPath[cur])
            cur = self.__resBfsPath[cur]
        return res[::-1]

    def getBfsOrder(self):
        for i in range(self.V):
            if not self.__visited[i]:
                self.__Bfs(i)
        #恢复初始值
        self.__visited = [False]*self.V#用来记录多个联通分量的首个Node或者可以说记录图中的节点是否被访问
        self.__BfsQue = deque(maxlen=self.V)
        self.__resBfs = []
        self.__resBfsPath = [-1]*self.V
        return self.__resBfs
    def __Bfs(self,v):
        self.__BfsQue.append(v)
        self.__visited[v] = True
        self.__resBfsPath[v] = -2
        while self.__BfsQue.__len__():
            node = self.__BfsQue.popleft()
            self.__resBfs.append(node)
            for i in self.cg.adjacentVertices(node):
                if not self.__visited[i]:
                    self.__BfsQue.append(i)
                    self.__resBfsPath[i] = node
                    self.__visited[i] = True

if __name__ == '__main__':
    s = solution(r"D:\tensorflow2_pytorch\python算法\Graph\ltflbl.txt")
    print(s.G)
    print("广度优先遍历:",s.getBfsOrder())
    print("0---->6BfsPath:",s.getBfspath(1,6))